package qjc.c_滑动窗口;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class b_找到字符串中所有字母异位词 {
    /**
     * 获取字符串 s 和 p 的长度，如果 s 的长度小于 p 的长度，直接返回空列表，
     * 初始化两个字符计数数组，用于存储 s 和 p 中字符的出现次数，
     * 初始化滑动窗口的前 pLen 个字符的计数，
     * 如果初始窗口的字符计数与 p 的字符计数相同，记录起始位置 0，
     * 滑动窗口遍历 s，移除窗口最左边的字符，添加窗口最右边的字符，
     * 如果当前窗口的字符计数与 p 的字符计数相同，记录起始位置 i + 1
     */
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new ArrayList<>();
        }
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; i++) {
            ++pCount[p.charAt(i) - 'a'];
            ++sCount[s.charAt(i) - 'a'];
        }
        List<Integer> result = new ArrayList<>();
        if (Arrays.equals(sCount, pCount)) {
            result.add(0);
        }
        for (int i = 0; i < sLen - pLen; i++) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];
            if (Arrays.equals(sCount, pCount)) {
                result.add(i + 1);
            }
        }
        return result;
    }
}
